package Tree;

import java.util.Stack;

public class TraverseTree {
	public static void main(String[] args){
		Node root = new Node(1);
		root.left = new Node(2);
		root.right = new Node(3);
		root.right.left = new Node(4);
		preOrder(root);
		System.out.println("===============");
		inOrder(root);
		System.out.println("===============");
		postOrderOneStack(root);
	}

	static void preOrder(Node root){
		if(root == null) return;
		Stack<Node> stack = new Stack<Node>();
		stack.push(root);
		while(!stack.isEmpty()){
			Node node = stack.pop();
			if(node.right != null){
				stack.push(node.right);
			}
			if(node.left != null){
				stack.push(node.left);
			}
			System.out.println(node.value);
		}
	}
	
	static void inOrder(Node root){
		if(root == null) return;
		Stack<Node> stack = new Stack<Node>();
		stack.push(root);
		Node current = root.left;
		while(true){
			//get down
			while(current != null){
				stack.push(current);
				current = current.left;
			}
			if(!stack.isEmpty()){
				current = stack.pop();
				System.out.println(current.value);
				current = current.right;
			}
			else break;
		}
	}
	
	static void postOrder(Node root){
		if(root == null) return;
		Stack<Node> stack1 = new Stack<Node>();
		Stack<Node> stack2 = new Stack<Node>();
		stack1.push(root);
		while(!stack1.isEmpty()){
			Node node = stack1.pop();
			stack2.push(node);
			if(node.left != null) stack1.push(node.left);
			if(node.right != null) stack1.push(node.right);
		}
		//print out stack2
		while(!stack2.isEmpty()){
			System.out.println(stack2.pop().value);
		}
	}
	
	static void postOrderOneStack(Node root){
		if(root == null) return;
		Stack<Node> stack = new Stack<Node>();
		stack.push(root);
		Node prev = null;
		while(!stack.isEmpty()){
			Node current = stack.peek();
			if(prev == null || current == prev.left || current == prev.right){
				//traverse down
				if(current.left != null){
					stack.push(current.left);
				}
				else if(current.right != null){
					stack.push(current.right);
				}
				else{
					System.out.println(current.value);
					stack.pop();
				}
			}
			else if(current.left == prev){
				//back from left child
				if(current.right != null){
					stack.push(current.right);
				}
				else{
					System.out.println(current.value);
					stack.pop();
				}
			}
			else if(current.right == prev){
				//back from right
				System.out.println(current.value);
				stack.pop();
			}
			prev = current;
		}
	}
}
